perm filename PUZZLE[W88,JMC] blob
sn#851114 filedate 1988-01-04 generic text, type C, neo UTF8
COMMENT ā VALID 00003 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00002 00002 puzzle[w88,jmc] Notes on 15 puzzle
C00003 00003 ā01-Jan-88 0950 AI.THROOP@R20.UTEXAS.EDU Stuck Tile and Bug Fix
C00016 ENDMK
Cā;
puzzle[w88,jmc] Notes on 15 puzzle
It looks like we need equivalence classes of positions.
Also more flexible restrictions to subsets of positions.
Also macros.
ā01-Jan-88 0950 AI.THROOP@R20.UTEXAS.EDU Stuck Tile and Bug Fix
Received: from R20.UTEXAS.EDU by SAIL.STANFORD.EDU with TCP; 1 Jan 88 09:50:29 PST
Date: Fri 1 Jan 88 11:50:45-CST
From: David Throop <AI.THROOP@R20.UTEXAS.EDU>
Subject: Stuck Tile and Bug Fix
To: jmc@SAIL.STANFORD.EDU
Message-ID: <12363168107.9.AI.THROOP@R20.UTEXAS.EDU>
I've been looking at a position which I call Stuck8. It occurs when
the 8-tile is in space 10 and the blank is in space 9. It occurs fairly
frequently in the solutions that I'm generating.
It takes the system ~2100 nodes, and a search to 22 ply, to find a
move combination that advances play. Finding a way out of this position
often dominates the quality of the answer - roughly a third of the
variation in the systems success at solving random boards turns on
whether in stumbles into this hole. This combination completes the 2nd
row - there are no intermediate states that are BETTER between the
position
1 2 3 4
5 6 7 11
:BLANK 8 10 12
14 9 13 15
and
1 2 3 4
5 6 7 8
:BLANK 12 10 11
14 9 13 15
However, there is a 13 move sequence that completes the 2nd row:
1 2 3 4
5 6 7 11
:BLANK 8 10 12
14 9 13 15
0 moves
1 2 3 4
5 6 7 11
14 8 10 12
:BLANK 9 13 15
1 moves
1 2 3 4
5 6 7 11
14 8 10 12
9 :BLANK 13 15
2 moves
1 2 3 4
5 6 7 11
14 8 10 12
9 13 :BLANK 15
3 moves
1 2 3 4
5 6 7 11
14 8 :BLANK 12
9 13 10 15
4 moves
1 2 3 4
5 6 7 11
14 :BLANK 8 12
9 13 10 15
5 moves
1 2 3 4
5 :BLANK 7 11
14 6 8 12
9 13 10 15
6 moves
1 2 3 4
5 7 :BLANK 11
14 6 8 12
9 13 10 15
7 moves
1 2 3 4
5 7 8 11
14 6 :BLANK 12
9 13 10 15
8 moves
1 2 3 4
5 7 8 11
14 6 12 :BLANK
9 13 10 15
9 moves
1 2 3 4
5 7 8 :BLANK
14 6 12 11
9 13 10 15
10 moves
1 2 3 4
5 7 :BLANK 8
14 6 12 11
9 13 10 15
11 moves
1 2 3 4
5 :BLANK 7 8
14 6 12 11
9 13 10 15
12 moves
1 2 3 4
5 6 7 8
14 :BLANK 12 11
9 13 10 15
13 moves
The system fails to find this combination for several reasons. First,
it breaks the two-row restriction - after moves 1, 2 and 3, the blank is
in the last row. Secondly, after move 5 it breaks the chain, making
tiles 5 and 6 non-contiguous. Thirdly, if the two-row restriction were
suspended, after move 5 there is an additional 5-move combination that
moves tile 8 into square 12 and decreases the Manhattan distance.
In general, I'm not a fan of the two-row restriction - it is true, in
the sense that a solution always does exist which doesn't violate it,
and it does prune a certain number of fruitless moves. But it also
prunes a lot of good moves, and leads to longer answers. I think that
the good it does could be done by a weaker rule.
We have already discussed the inefficiency caused by using the whole row
as the chain, rather than just its last two elements.
For now, we could probably live with the inefficiency caused by the
Manhattan Distance getting greedy and leading to a suboptimal solution.
The important thing seems to be to allow the intermediate islands so
that this one problem doesn't so dominate the search.
=================================
BUG!
The code for Manhattan-Distance should read
(def-better-heuristic Manhattan-distance (newboard oldboard)
(let* ((nexttile (1+ (board-completed-chain oldboard)))
(currentpos (current-position nexttile oldboard)))
(unless (equal (position-contents currentpos newboard) ; If the tile hasn't changed position,
nexttile) ; don't calc the manhattan distance.
(and
(> (man-dist nexttile currentpos (board-side oldboard))
(man-dist nexttile (current-position nexttile newboard)
(board-side oldboard))) ; The final = test checks to prohibit undoing
(>= (completed-chain newboard) ; the existing complete chain.
(board-completed-chain oldboard)))) ; ERROR WAS IN THIS LINE.
))
This change only seems to make small differences in efficiency in most
positions.
David
-------
ai.throop@r20.utexas.edu
15 puzzle
I have understood your message and am ready to talk. What times and what
numbers are good for calling you? I agree that the present way of solving
the problem is suboptimal and have several ideas. It looks like the
simple better-worse system is not good enough to express the human
heuristics even though it is good enough to solve the puzzle. My ideas
involve some of
1. equivalence classes of positions
2. more flexible restrictions to subsets of positions
3. macromoves. This is the one that offers me the most difficulty.
Consider *blocked-4*. Imagine that we restrict the blank to the
last 2 columns and first 3 rows, i.e. to 6 squares arranged vertically.
We consider cyclically permuted postions as equivalent, and we don't
care about the positions of any tiles except those we are trying to
get in the right places now, i.e. tiles 3 and 4. We also don't care
about the location of the blank. Then the space of
equivalence classes has exactly 4 members. An equivalence class is
characterized by the number of other tiles between 3 and 4 in clockwise
order and this number is in the set {0,1,2,3}. Each move in this space
increases or decreases the number by 1. Our goal is that the number
should be 0. However, each move
in this space corresponds to several moves in the original space, i.e.
to a macro, because we have to rotate the configuration in order to
make the change.
I think the above concepts are not peculiar to the 15 puzzle.